\section{The Game} % (fold)
\label{sec:simulation}

\subsection{Pairs} % (fold)
\label{sub:pairwise_traversal}
Since nodes have well-defined utility functions, it is possible to allow the nodes of the network to play a game where they add and drop edges in order to increase their utility.

The first problem encountered in defining such a relationship game is choosing who the agents are. Having each node act independently as an agent for classic best-response dynamics seems to violate the idea that relationships are mutual: how can one person unilaterally create a friendship? Our workaround is to model relationships as a sequential game where, on its turn, each pair of nodes decides whether or not there should be an edge between them. The algorithm for running a step of the game (a unit in which every pair takes its turn once) is is given below.

% Pairwise Step algorithm (fold)
\restylealgo{algoruled}
\begin{algorithm}[h!]
	\dontprintsemicolon
	\SetKwInput{Input}{input}
	\SetKwData{Utility}{utility}
	\SetKw{pIf}{if}
	\SetLine
	\caption{Running one step of the game}
	\Input{a social network $N$}
	
	\ForEach{distinct pair of nodes $(a, b)$ in $N$}{
		$u_a\leftarrow$ the utility of $a$ \tcp{$u(a)$}\;
		$u_b\leftarrow$ the utility of $b$ \tcp{$u(b)$}\;
		
		\eIf{an edge exists between $a$ and $b$}{
		  \tcp{disconnect the nodes if it would be beneficial to either $a$ or $b$}
			$u_a\prime{}\leftarrow$ the utility that $a$ would have if the $a$--$b$ edge were removed\;
			$u_b\prime{}\leftarrow$ the utility that $b$ would have if the $a$--$b$ edge were removed\;
			disconnect $a$ and $b$ \pIf{$u_a\prime{} > u_a$ {\bf or} $u_b\prime{} > u_b$}\;
		}{
		  \tcp{connect the nodes if it would be beneficial to both $a$ and $b$}
			$u_a\prime{}\leftarrow$ the utility that $a$ would have if an $a$--$b$ edge were added\;
			$u_b\prime{}\leftarrow$ the utility that $b$ would have if an $a$--$b$ edge were added\;
			connect $a$ and $b$ \pIf{$u_a\prime{} > u_a$ {\bf and} $u_b\prime{} > u_b$}\;
		}
	}
	\label{alg:pairwise_step}
\end{algorithm}
% algorithm pairwise_step (end)

% subsection pairwise_traversal (end)

\subsection{Stability} % (fold)
\label{sub:stability}
Let us consider the possible moves from a graph. An edge that would be added at some $\widehat{\alpha}$ will also be a beneficial move whenever $\alpha \leq \widehat{\alpha}$, because the two nodes incident to the edge could only gain more utility on those $\alpha$. Likewise if an edge would be dropped at some $\widehat{\alpha}$, the drop would only benefit the incident edges more when $\alpha \geq \widehat{\alpha}$. This leads to the notion of a \emph{stable $\alpha$ range}: by finding the lowest $\alpha$ at which an edge drop would occur, $\alpha_{-}$ and finding the highest $\alpha$ at which an edge addition, $\alpha{+}$ would occur. If $\alpha{+} \leq \alpha{-}$ then the graph will be stable on any $\alpha$ between the two. If a stable $\alpha$ range exists for a graph $G$, then we say that $G$ is a \emph{stable graph}.

Additionally let us indicate some notation that will be used when studying the stability of graphs. For some node $a$ on graph $G=\langle{}V,E\rangle{}$, $v(a)$ is the value of $a$ on G. Likewise $u(a)$ is the utility, value minus cost, of $a$ on G. $u_{+\langle{}a,b\rangle{}}(a)$ is the utility that $a$ has on the graph $\langle{}V, E \cup {\langle{}a,b\rangle{}}\rangle{}$ and $u_{-\langle{}a,b\rangle{}}(a)$ is the utility that $a$ has on the graph $\langle{}V, E - {\langle{}a,b\rangle{}}\rangle{}$. ${\Delta}v_{+\langle{}a,b\rangle{}}(a)$ is the change in value for $a$ from G to $\langle{}V,E \cup {\langle{}a,b\rangle{}}\rangle{}$ and likewise for ${\Delta}v_{-\langle{}a,b\rangle{}}(a)$.

% subsection stability (end)

\subsection{Behavior} % (fold)
\label{sub:behavior}
\subsubsection{Order matters} % (fold)
\label{ssub:order_matters}
The final graph that results from network formation depends heavily on the order in which nodes are chosen. An example of an unstable intermediate graph that can produce a number of stable outcome graphs is given in figure \ref{fig:chaos}.

\begin{figure}[H]
  \centering
  
  \pgfdeclarelayer{background}
  \pgfsetlayers{background,main}
  
  \begin{tikzpicture}
    \node [normalnode] (3) {3};
    \node [normalnode,above left=of 3] (2) {2};
    \node [normalnode,above right=of 2,xshift=-7mm] (1) {1};
    \node [normalnode,above right=of 3] (4) {4};
    \node [normalnode,above left=of 4,xshift=7mm] (5) {5};
    
    \draw (1) -- (2);
    \draw (4) -- (5);
    
    \begin{scope}[xshift=-6cm]
      \node [normalnode] (3') {3};
      \node [normalnode,above left=of 3'] (2') {2};
      \node [normalnode,above right=of 2',xshift=-7mm] (1') {1};
      \node [normalnode,above right=of 3'] (4') {4};
      \node [normalnode,above left=of 4',xshift=7mm] (5') {5};

      \draw (4') -- (1') -- (2') -- (4');
      \draw (3') -- (4') -- (5');
    \end{scope}
    
    \begin{scope}[xshift=6cm]
      \node [normalnode] (3'') {3};
      \node [normalnode,above left=of 3''] (2'') {2};
      \node [normalnode,above right=of 2'',xshift=-7mm] (1'') {1};
      \node [normalnode,above right=of 3''] (4'') {4};
      \node [normalnode,above left=of 4'',xshift=7mm] (5'') {5};

      \draw (2'') -- (4'') -- (5'') -- (2'') -- (1'') -- (3'') -- (5'');
      \draw (4'') -- (3'');
    \end{scope}
    
    \begin{pgfonlayer}{background}
      \node (init) [fill=black!10,rounded corners,fit=(1)(2)(3)(4)(5)] {};
      \node (a) [fit=(1')(2')(3')(4')(5')] {};
      \node (b) [fit=(1'')(2'')(3'')(4'')(5'')] {};
    \end{pgfonlayer}
    
    \draw [-to,line width=2pt,shorten >=2mm,shorten <=2mm] (init) -- (a)
      node [above=1mm,midway] {\textsf{\bfseries ?}};
    \draw [-to,line width=2pt,shorten >=2mm,shorten <=2mm] (init) -- (b)
      node [above=1mm,midway] {\textsf{\bfseries ?}};
  \end{tikzpicture}
  \caption{\label{fig:chaos}An unstable graph whose eventual stable state after playing the formation game depends on the order in which pairs are chosen. In most cases, the graph on the left results. If pairs involving node 3 go first, the graph on the right can result.}
\end{figure}
% subsubsection order_matters (end)

\subsubsection{Termination} % (fold)
\label{ssub:termination}
Configurations of nodes that never result in a stable graph appear to be rare, but are possible. One example is given in figure \ref{fig:endless}.

\begin{figure}[ht!]
  \centering
  
  \begin{tikzpicture}
    \node [normalnode] (4) {4};
    \node [normalnode,below left=of 4] (5) {5};
    \node [normalnode,below right=of 4] (6) {6};
    \node [normalnode,right=of 6] (2) {2};
    \node [normalnode,below=of 5] (1) {1};
    \node [normalnode,below=of 6] (3) {3};
    
    \draw (2) -- (6) -- (3) -- (1) -- (5) -- (4) -- (6) -- (5);
  \end{tikzpicture}
  \caption{\label{fig:endless}When all of these nodes are in the same cluster with an edge cost of (for example) $\frac{3}{10}$, and pairs are always given turns in numerical order, the game does not terminate. It returns to this unstable configuration after 6 steps.}
\end{figure}
% subsubsection termination (end)

\subsubsection{Tails} % (fold)
\label{ssub:tails}
Earlier in section \ref{sub:standard_model}, we noted that because of our value function's method of dealing with multiple shortest paths between two nodes, it is possible for a node to lose value by creating a redundant connection. This leads to a structure that we call a \emph{tail}. An example of a network with a tail is shown in figure \ref{fig:graph_with_tail}.

\begin{figure}[h!]
  \centering
  \begin{tikzpicture}
    \foreach \i in {0,...,6}
    {
      \path (90+60*\i:12mm) node (\i) [normalnode] {};
    }
    \path (0:25mm) node (loner) [focusnode] {};
    
    \draw (1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (1) -- (3) -- (5) -- (1)
      -- (4);
    \draw (2) -- (6) -- (4) -- (2) -- (5);
    \draw (3) -- (6);
    \draw (loner) -- (5);
    \draw [dashed] (loner) -- (4);
  \end{tikzpicture}
  \caption{A single-cluster network with a tail: if the red node on the far right adds an edge to any other node, it would make its connections to the other four nodes in the clique redundant, reducing their value. The reduction is enough that this network is stable.\label{fig:graph_with_tail}}
\end{figure}

The network shown in the figure is stable. The node on the tail is not willing to add any more edges, because by adding any one edge to a member of the clique on the left, the node would make its connections to the other four members of the clique redundant, decreasing their value. The value reduction is significant enough that the node on the tail would lose utility by adding such an edge (i.e., the extra value from its new direct connection would be more than offset by the cost of the new edge and the value reduction from the redundancy).

The fact that tails are stable (and form somewhat often in our game) is probably not a desirable property. A person evaluating a network like the one shown in figure \ref{fig:graph_with_tail} would probably conclude either that there is a structural hole between the clique and the node on the tail, or that the node on the tail is somehow an undesirably person. Either conclusion would be false.
% subsubsection tails (end)

\subsubsection{Connectedness} % (fold)
\label{ssub:connectedness}
Generally, our game satisfies our goal (see section \ref{sub:model_goals}) of creating networks where everyone is connected. However, there are some special cases where this does not occur. It is possible to create a graph where all the nodes in a connected component are experiencing negative utility, but refuse to drop any edges. In our game, nodes can only drop one edge at a time, so when any of the nodes with negative utility consider dropping one of their edges, they find that their utility would become even more negative. They cannot ``think ahead'' about the possibility of dropping many edges, and as a result, they do not drop any.

In these cases, it can also be true that nodes outside of that component are unwilling to connect to it. For an example of this, see false conjecture \ref{connectivity} in section \ref{sec:theorems-and-conjectures}. For brief discussion of a model where this scenario is impossible, see section \ref{ssub:multi_drop}.
% subsubsection connectedness (end)
% subsection behavior (end)

\subsection{Alternate Models} % (fold)
\label{sub:alternate_models}
\subsubsection{Unilateral versus Bilateral Connections}
\label{ssub:unilateral}
In the unilateral model, one node may create an edge with any other node. The original node pays all of the cost, but both nodes benefit from the connection. As can be seen in the following example, a node can lose utility from a connection made to it, even though it pays nothing.

\begin{figure}[H]
  \centering
  \begin{tikzpicture}[point/.style={coordinate},thick,draw=black!50]
    \node [matrix,column sep=5mm,normalnode/.append style={minimum size=7mm}]
    {
      & \node [normalnode] (1) {c}; & \node [normalnode] (2) {d}; & & & & & \\
      \node [normalnode] (a) {a}; & & & \node [point] {}; & \node [point] {}; &
      \node [point] {}; &\node [point] {}; &\node[manynodes] (c) {$K_{100}$}; \\
      & \node [normalnode] (b) {b}; & \node [normalnode] (3) {e}; & & & & & \\
    };
    
    \draw (a) -- (1) -- (2);
    \draw (b) -- (3);
    
    \draw (2) -- (c.north west);
    \draw (2) -- (c.west);
    \draw (2) -- (c.south west);
    \draw (3) -- (c.north west);
    \draw (3) -- (c.west);
    \draw (3) -- (c.south west);
    
    \draw [dashed] (a) -- (b);
  \end{tikzpicture}
  \caption{A graph illustrating a case in the unilateral model when adding an edge to a node can decrease that node's value. (Nodes $d$, $e$, and all of the nodes in the yellow $K_{100}$ blob together form a clique.)}
\end{figure}

Currently: $v(a) = \frac{1}{2} + \frac{100}{3} + \frac{1}{103} + \frac{1}{104} + \frac{1}{105} = 33.86$. If $a$ makes an edge to $b$ then $v_{+\{a,b\}}(a) = \frac{2}{2} + \frac{101}{3} + \frac{1}{105} = 34.68$ so $a$ will make the connection when $\alpha$ is less than 0.81. Now consider $b$: $v(b) = \frac{1}{2} + \frac{1}{3} + \frac{100}{4} + \frac{1}{104} + \frac{1}{105} = 25.85$ and $v_{+\{a,b\}}(b) = \frac{2}{2} + \frac{2}{3} + \frac{100}{6} = 18.33$. So the value for $b$ decreases after this connection is made to it. This model was abandoned after this discovery  for two reasons. First if an edge were made from $a$ to $b$, $b$ would drop the edge on its next move only to have $a$ add the edge again on the move after that. Also, the nodes are supposed to represent people who are trying to maximize their own utility, so it is unnatural to give a person no say in the creating of a relationship that will decrease his utility.

\subsubsection{Multi-Drop versus Single-Drop} % (fold)
\label{ssub:multi_drop}
In the standard model, a turn consists of adding or removing a single edge. In the multi-drop model, a move consists of adding a single edge or removing any number of edges from a single node. 

A simple result of this model is that no node has negative utility in a stable graph. Whenever a node has negative utility, it can always drop all of its edges to achieve a utility of zero.

In any graph $G$, where $\alpha_{-}^{m}$ is the lowest $\alpha$ at which any node will drop some number of edges on the multi-drop model and $\alpha_{-}^s$ is the same for the single drop model; $\alpha_{+}^m$ is the highest $\alpha$ at which an edge will be added in the multi-drop model and $\alpha_{+}^s$ is same for the single drop model, $\alpha_{-}^m \leq \alpha_{-}^s$, but $\alpha_{+}^m = \alpha_{+}^s$ (Theorem \ref{dropthm}. Remember that when $\alpha_{+} \leq \alpha_{-}$ for some graph we say the graph is stable. Since $\alpha_{+}$ is the same in both models, but $\alpha_{-}^m \leq \alpha_{-}^s$, all graphs that were unstable in the single-drop model will be unstable in the multi-drop model. Additionally graphs that were stable in the single-drop model may have smaller stable $\alpha$ ranges or may become unstable.
% subsubsection multi_drop (end)
% subsection alternate_models (end)

% section simulation (end)